Current computer systems suffer from an imbalance between central processor unit (host) and input/output (I/O) performance. In recent years, host speed has increased tremendously. However, during the same period, the I/O speed of secondary storage devices, such as disk drives has not kept pace.
Whereas host performance is, to a large extent, related to the speed of its electronic components, disk drive I/O performance is dominated by the time it takes for the mechanical parts of the disk drives to move to the locations where data are stored. The time required to position a read/write head relative to the recording surfaces of a disk drive is generally known as the seek time. Seek times for random accesses to data stored on disk drives are, on the average, orders of magnitude longer than the time it takes to actually transfer the data between the host and the disk drives.
Prior art disk drives have provided a buffer between the host and the disk drives to improve I/O speed. Such an buffer is typically in the form of a memory cache (cache) to take advantage of the principles of locality of reference, which are well-known in computer programming. These principles indicate that when data stored at one location are accessed, there is a high probability that data stored at physically adjacent locations will be accessed soon afterwards in time.
A typical prior art cache stores disk drive data in semiconductor memory, which has relatively fast access time, when compared to the seek time of disk drives. During the operation of the computer system, data transfers between the host and the disk drives are buffered through the cache. For example, during a read operation, the data are first read into the cache before being transferred to the host, and during a write operation, the data are stored in the cache before the data are written to the disk drives. Thus, as long as the data remain in cache, I/O requests are serviced by cache instead of by the disk drive.
By having a cache as an interface between the host and the disk drives, the number of disk I/O transfers are reduced since there is a high probability that the data accessed are already stored in cache. In other words, only a fraction of the number of I/O requests for disk data initiated by the host, hereinafter "host I/O requests," will actually result in physical "disk I/O requests" with inherently long access or latency times. In other words, if the requested data are already in cache, the host I/O request will not result in a physical I/O request. That is, a cache increases the ratio of relatively fast host I/O requests to relatively slow disk I/O requests to improve overall I/O performance.
Write data stored in cache are susceptible to corruption or total loss due to component or power failures until written to disk. Therefore, write cache is generally non-volatile memory. However, high speed non-volatile memory is relatively expensive, and therefore, cost constraints influence the size of cache.
The management of the cache is a major operational bottleneck for computer systems having multiple concurrent users and a large number of data files. Since the data storage capacity of cache is generally only a fraction of the total storage capacity of the disk drives, cache space must be managed. As cache is filled with data to be written to the disk drives, additional space must be made available for new data. Typical prior art system write data from cache to the disk drives in a least recently used (LRU) manner. An LRU algorithm frees cache space by writing older or least recently used to disk before newer or most recently used data (MRU) to increase the likelihood of accessed data being in cache.
Another consideration in managing cache space is the amount of memory space that is individually allocatable to users for a data transfer. Most modern disk drives can transfer large amounts of data, or multiple disk sectors with a single physical I/O request. Also, the amount of data which are read by a random access database application are generally substantially larger than the amount of data that are modified or written. Based on these factors it would seem that the individually allocatable amounts of memory space should be sized relatively large.
However, by having the allocatable amounts of memory space relatively large, the quantity of individually allocatable amounts of memory space for users is decreased, which increases the rate of cache depletion, locking out other users, and decreases the computer system I/O throughput. Therefore, cache space is usually organized in individually allocatable amounts of memory space which are sized relatively small. For example, allocatable cache memory space is frequently sized to the minimum amount of data which can be transferred to and from the disk drive with a single physical I/O request, for example, a sector. This minimally sized amount of individually allocatable memory space will be referred to hereinafter as a "block."
To reduce the rate of physical I/O transfers due to smaller cache blocks, some prior art systems combine or merge cache blocks during a physical I/O write request as follows. When additional memory space is needed in the cache to store new data, a search is made in the cache to identify the LRU block. The LRU block is the block storing data least recently used by the host, used meaning any read or write access to any of the data stored in a block. After the LRU block has been identified, a second search is made in cache to identify any other blocks which store data which are destined for sectors which are physically contiguous with the sector of the LRU block. All blocks thus identified are then merged into a single larger data segment which is written to the disk drive with a single physical I/O request. Thus, not only are the number of physical I/O requests reduced, but also additional cache memory space is made available for new data. However, even with block merging, the number of physical I/O request are still more than the optimal number that could potentially be achieved with larger blocks and a more expensive larger cache.
Accordingly a system is needed for use with disk drives of a computer system which is capable of supporting a large number of users without an increase in cost of cache memory, and yet has a substantial improvement in I/O performance.